The present invention relates to stochastic screens for printing and more particularly to a method for generating stochastic screens.
Ever since the introduction of printing centuries ago, the representation of shades has presented a particular challenge to printers. The problem is simple: most printers cannot vary the strength of ink laid down at any given point on the paper, yet many candidates for printing require varying tonal quality to represent the original image.
The solution generally employed is to print a mixture of inked and non-inked areas sufficiently close together that the viewer does not perceive the separate areas but instead sees a uniform area of a tone that is a mixture of the ink and the paper tones. Commonly, this technique is termed halftoning. It has been used from earliest times in wood-block prints, down to the present day computer laser and ink-jet printers.
With halftoning there is a loss of spatial resolution. Therefore, the ideal halftone patterns would mix ink and paper areas very finely to preserve as much spatial detail as possible. However, most printing technology is not capable of printing very fine dots of ink. There will be a certain minimum size of ink dot below which the ink does not fix reliably to the paper. Also, there may be a certain variation in the quantity of ink laid down around the margin of the dot, requiring a certain minimum area of ink to reduce the variation to acceptable levels. Thus, there is usually a compromise between fine mixing to preserve spatial resolution and coarse mixing to give reliable halftones.
Traditionally the areas of ink have been arranged in regular (or ordered) patterns. However, if the areas are fine enough it is possible to arrange them in irregular patterns.
The terms ordered screen and stochastic screen are applied here respectively to these two approaches. Each approach introduces some xe2x80x9cnoisexe2x80x9d (that is, distortion) to the original image when imposing the halftone patterns. Characteristically, ordered screens add a uniform noise at the frequency of the pattern, whereas stochastic screens, due to their irregular nature, can add noise at many different frequencies. The challenge in producing a stochastic screen is to avoid introducing noise at the lower, more noticeable frequencies.
For our purposes a screen is implemented as a two dimensional grid of values such as is illustrated in FIG. 1. Each value within the grid determines the halftones for which a dot will be placed on the paper. This is achieved by comparing the tonal value of each point (or picture element, or pixel) of the image with the corresponding grid value and printing a dot, or not, depending on which is the larger value. In other words, the screen value gives the tone threshold at which the dot is turned on.
This approach ensures that patterns do not xe2x80x9cshiftxe2x80x9d and change between different tones, which could introduce unintentional noise. However, it also places a constraint on the arrangement of dots in each successive halftone as it xe2x80x9cinheritsxe2x80x9d an initial pattern from its predecessor.
The grid is of arbitrary size though it is preferable to have the same number of dots turned on at each halftone.
To apply the screen across an image of arbitrary size, the grid is tiled to cover the whole image surface.
According to a first aspect of the present invention there is provided a method of generating a method of generating a stochastic screen for use in printing a halftone containing image on a surface, where the generated stochastic screen comprises an array of threshold values each of which represents a halftone threshold at which pixels are printed at the corresponding location, the method comprising:
a) entering a first threshold value into the array;
b) for a first halftone level, defining a number of threshold values to be entered into the array and, for each threshold value to be placed,
for each of a number of candidate locations in the array, computing a distance function between the candidate location and the locations of threshold values already placed into the array, and placing the threshold value into the array at a location for which the distance function is substantially minimised, and
c) repeating step b) for each subsequent halftone level.
In certain embodiments of the present invention, said distance function incorporates a weighting function which acts to increase the contribution to the distance function of threshold values close to the candidate location at the expense of threshold values further from the candidate location. Preferably, the weighting function acts to exclude threshold values placed outside a predefined radius R from the candidate location, from the distance function calculation.
According to a second aspect of the present invention there is provided a method of printing an image on a surface, the method comprising mapping one or more stochastic screens, generated according to the method of the above first aspect of the invention, to the surface, and printing a pixel onto the surface only if the halftone value of the pixel exceeds the halftone threshold value at the equivalent location in a mapped stochastic screen.
According to a second aspect of the present invention there is provided a data storage medium having stored thereon a computer program which when run on a computer provides a driver for driving a printer coupled to the printer, the driver comprising one or more stochastic screens generated using the method of the above first aspect of the invention.